%0 Conference Proceedings
%4 sid.inpe.br/sibgrapi@80/2008/07.18.15.09
%2 sid.inpe.br/sibgrapi@80/2008/07.18.15.09.34
%@doi 10.1109/SIBGRAPI.2008.24
%T Tradeoffs in approximate range searching made simpler
%D 2008
%A Arya, Sunil,
%A Fonseca, Guilherme D. da,
%A Mount, David M.,
%@affiliation The Hong Kong University of Science and Technology
%@affiliation University of Maryland
%@affiliation University of Maryland
%E Jung, Cláudio Rosito,
%E Walter, Marcelo,
%B Brazilian Symposium on Computer Graphics and Image Processing, 21 (SIBGRAPI)
%C Campo Grande, MS, Brazil
%8 12-15 Oct. 2008
%I IEEE Computer Society
%J Los Alamitos
%S Proceedings
%K range searching, geometric approximation, geometric data structures, computational geometry.
%X Range searching is a fundamental problem in computational geometry. The problem involves preprocessing a set of n points in R^d into a data structure, so that it is possible to determine the subset of points lying within a given query range. In approximate range searching, a parameter eps > 0 is given, and for a given query range R the points lying within distance eps diam(R) of the range's boundary may be counted or not. In this paper we present three results related to the issue of tradeoffs in approximate range searching. First, we introduce the range sketching problem. Next, we present a space-time tradeoff for smooth convex ranges, which generalize spherical ranges. Finally, we show how to modify the previous data structure to obtain a space-time tradeoff for simplex ranges. In contrast to existing results, which are based on relatively complex data structures, all three of our results are based on simple, practical data structures.
%@language en
%3 tradeoffs-final.pdf